// 左右双指针
// 利用数组的单调性，配合左右双指针，遍历一遍数组，完成题目要求
// 可以从题目的暴力解法入手，双指针的解法通常可以少遍历一遍数组，将时间复杂度降低O(N)

// 例题 5：
//给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
//        示例 1:
//        输入: nums = [2,2,3,4]
//        输出: 3
//        解释:有效的组合是:
//        2,3,4 (使用第一个 2)
//        2,3,4 (使用第二个 2)
//        2,2,3

//        示例 2:
//        输入: nums = [4,2,3,4]
//        输出: 4

//        提示:
//        1 <= nums.length <= 1000
//        0 <= nums[i] <= 1000

// 解题思路：
//  首先对数组进行排序，让数据具备单调性，利用两边和大于第三边解决问题
//  其次固定最后一个数，作为三角形的第三条边， nums[left] 和 nums[right] 作为第一条边和第二条边
//  如果 nums[left] + nums[right] > 第三条边 ，都能构成三角形，ret += (right - left), right--
//  如果 nums[left] + nums[right] <= 第三条边，都不能构成三角形， ret += 0, left++

import java.util.Arrays;

public class TriangleNumber {
    public int triangleNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int ret = 0;
        for(int i = n - 1; i >= 2; i--){
            int left = 0;
            int right = i - 1;
            while(left < right){
                if(nums[left] + nums[right] > nums[i]) {
                    ret += (right - left);
                    right--;
                }else left++;
            }
        }
        return ret;
    }
}
